package topic.linklist;

/**
 * 面试题 02.05. 链表求和
 * https://leetcode-cn.com/problems/sum-lists-lcci/
 */
public class AddTwoNumbers {
    public static void main(String[] args) {
        addTwoNumbers(LinkListFactory.getFirstListNode(), LinkListFactory.getSecondListNode());
    }

    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(-1);
        ListNode prv = head;
        // 进位标志
        int carry = 0;
        int sum = 0;
        while(l1 != null || l2 != null) {
            // 当两个链表长度不等时需要补0
            int a = l1 == null ? 0 : l1.val;
            int b = l2 == null ? 0 : l2.val;
            sum = a + b + carry;
            // 设置进位标志
            carry = sum / 10;
            if (sum >= 10) {
                sum = sum % 10;
            }
            // 产生新节点
            ListNode curr = new ListNode(sum);
            // 头节点指向当前节点
            head.next = curr;
            // 移动到当前节点
            head = curr;
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }
        // 标志和产生进位，大于链表数字长度，需加新节点
        if (carry == 1) {
            head.next = new ListNode(carry);
        }
        return prv.next;
    }
}
